/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.graph.bfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * <p>
 * 单词变换返回最小变换路径[广度优先搜索]
 * 
 * 输入: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] 
 * 输出：5 因为"hit" -> "hot" -> "dot" -> "dog" -> "cog" 不存在路径返回0，字典的单词都具有相同的长度
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月28日
 */
public class WordLadder {
    //广度优先遍历，使用两个队列，分别记录当前遍历的节点和下一轮需要遍历的节点
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        
        Queue<String> curQue = new LinkedList<String>();
        Set<String> used = new HashSet<>();
        //加上初始单词
        used.add(beginWord);
        curQue.add(beginWord);
        int count = 1;
        if(beginWord.equalsIgnoreCase(endWord)){
            return count;
        }
        while(curQue.size()>0){
            Queue<String> nextQue = new LinkedList<String>();
            count++;
            while(curQue.size()>0){
                String word = curQue.poll();
                //获取单词的所有变体
                for(String transform:getTransform(word,used,wordDict,endWord)){
                    if(transform.equalsIgnoreCase(endWord)){
                        return count;
                    }
                    //加入下一轮的单词
                    nextQue.add(transform);
                }
            }
            //复制下轮结果
            curQue = nextQue;
        }
        return 0;
    }

    /**
     * 获取单词的所有变体
     * @param word 
     * @param used
     * @param dict
     * @param end
     * @return
     * @author towan
     * 2015年5月28日
     */
    private List<String> getTransform(String word, Set<String> used, Set<String> dict, String end) {
        List<String> result = new ArrayList<String>();
        char[] letters = word.toCharArray();
        for(int i=0;i<letters.length;i++){
            //每个字母做替换
            char ori = letters[i];
            for(char c='a';c<='z';c++){
                if(ori !=c){
                    //替换字符
                    letters[i] = c;
                    String trans = new String(letters);
                    if(trans.equalsIgnoreCase(end) || (!used.contains(trans) && dict.contains(trans))){
                        //变体为第二个单词，在字典且没有使用过，那么加入
                        used.add(trans);
                        result.add(trans);
                    }
                }
            }
            //恢复原来字符
            letters[i] = ori;
        }
        return result;
    }

}
